package LeetCode;

import java.util.Arrays;

public class LC_581_ShortestUnsortedContinuousSubarray {

    public static void main(String[] args) {

    }

    class Solution {
        public int findUnsortedSubarray(int[] A) {
            int n = A.length, beg = -1, end = -2, min = A[n - 1], max = A[0];
            for (int i = 1; i < n; i++) {
                max = Math.max(max, A[i]);
                min = Math.min(min, A[n - 1 - i]);
                if (A[i] < max) end = i;
                if (A[n - 1 - i] > min) beg = n - 1 - i;
            }
            return end - beg + 1;
        }
    }

    class Solution_2 {
        public int findUnsortedSubarray(int[] nums) {
            int[] temp = new int[nums.length];
            System.arraycopy(nums, 0, temp, 0, nums.length);
            Arrays.sort(temp);
            int start = 0, end = nums.length - 1;
            while (start < nums.length && temp[start] == nums[start]) start++;
            while (end > start && temp[end] == nums[end]) end--;
            return end + 1 - start;
        }
    }

}